/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/strstr-ii
   @Language: C++
   @Datetime: 19-04-04 10:42
   */

// Method 1, using c strstr
class Solution {
public:
	/*
	 * @param source: A source string
	 * @param target: A target string
	 * @return: An integer as index
	 */
	int strStr2(const char* source, const char* target) {
		// write your code here
		if(source==NULL || target==NULL) return -1;
		const char *ch=strstr(source,target);
		return ch!=NULL?ch-source:-1;
	}
};


// Method 2, using KMP
class Solution {
	void getnext(const char* target, int *next){
		int lt=strlen(target);
		next[0]=-1;
		for(int i=0, j=-1; i<lt;){
			if(j==-1 || target[i]==target[j]){
				++i, ++j;
				next[i]=(target[i]==target[j]?next[j]:j);
			}
			else j=next[j];
		}
	}
public:
	/**
	 * Returns a index to the first occurrence of target in source,
	 * or -1  if target is not part of source.
	 * @param source string to be scanned.
	 * @param target string containing the sequence of characters to match.
	 */
	/** Tips: The classical KMP and optimize the next[]
	 * Source String: a b a c a a b a c a b a a b b
	 * Target String: a b a c a b
	 * using index i refers to S, j refers to T, begin from 0
	 * when match the 5th char, S is 'a' otherwise T is 'b',
	 * traditional method is to rematch from 1th char 'b' (i=1,j=0)
	 *
	 * Why don't match current next : i=6,j=0?
	 * Because the S[2] equal to T[0], may match the T. And Why? 
	 * Because the T has same char such as 'a', 'b'.
	 *
	 * If the T is "abcdef", S is "abcdekabcd": match the 5th failure,
	 * We don't need remove the i to range [0,4], 
	 * just match next : i=6, and j=0
	 *
	 * So, KMP idea do process for Target, and calculate that
	 * when match failure, the next match refers to where.
	 *
	 * I'll write a note for KMP details later.
	 * */
	int strStr2(const char* source, const char* target) {
		// write your code here
		if(source==NULL || target==NULL) return -1;
		int ls=strlen(source), lt=strlen(target);
		int *next=(int*) malloc(sizeof(int)*(lt+1));
		getnext(target,next);
		int i=0, j=0;
		while(i<ls && j<lt){
			if(j==-1 || source[i]==target[j]) ++i, ++j;
			else j=next[j];
		}
		free(next);
		return j==lt?i-lt:-1;
	}
};
